#ifndef __ARBOL__CATEGORIAS__H__
#define __ARBOL__CATEGORIAS__H__

#include <string.h>
#include "Tipos.h"
#include "DiccTrie.h"
#include "modulos/aed2/Lista.h"

/**
 * Implementación de ArbolCategorias.
 *
 * Implementa el árbol de categorías del TP2.
 */
class ArbolCategorias {
	public:
		/**
		 * Crea un árbol de categorías.
		 * @param[in] raiz El nombre de la categoría raíz.
		 * @pre @b raíz no puede ser la cadena vacía.
		 * @remark @b Complejidad: \f$\Theta(|raiz|)\f$
		 */
		ArbolCategorias( const String &raiz );

		/**
		 * Destruye un árbol de categorías.
		 * @remark @b Complejidad: \f$\Theta(n)\f$, donde @b n es la cantidad de categorías.
		 */
		~ArbolCategorias();

		/**
		 * Agrega una categoría al árbol.
		 *
		 * @param[in] padre El padre de la categoría que se está agregando.
		 * @param[in] hija La categoría a agregar.
		 * @pre @b padre tiene que pertenecer al árbol de categorías.
		 * @pre @b hija no puede pertenecer al árbol de categorías.
		 * @pre @b hija no puede ser la cadena vacía.
		 * @remark @b Complejidad: \f$\Theta(|padre|+|hija|)\f$
		 */
		void Agregar( const String &padre, const String &hija );

		/**
		 * Obtiene la raíz del árbol de categorías.
		 * @remark @b Complejidad: \f$\Theta(1)\f$
		 * @remark @b Alias: Devuelve una referencia constante al nombre de la categoría raíz.
		 * @returns El nombre de la categoría raíz.
		 */
		const String &Raiz() const;

		/**
		 * Obtiene el padre de una categoría
		 * @param[in] hija La categoría de la cual obtener su padre.
		 * @remark @b Complejidad: \f$\Theta(|hija|)\f$
		 * @remark @b Alias: Devuelve una referencia constante al nombre de la categoría padre.
		 * @returns El nombre de la categoría padre
		 */
		const String &Padre( const String &hija ) const;

		/**
		 * Obtiene el ID de una categoría.
		 * @param[in] cat El nombre de la categoría de la cual queremos saber su id.
		 * @remark @b Complejidad: \f$\Theta(|cat|)\f$
		 * @returns El id de la categoría.
		 */
		Nat Id( const String &cat ) const;

		/**
		 * Obtiene la cantidad de categorías en el árbol.
		 * @remark @b Complejidad: \f$\Theta(1)\f$
		 */
		Nat CantCategorias() const;

	private:
		/** Un nodo del árbol */
		struct Nodo {
			/** Crea un nodo.
			 * @param[in] id Id de la categoría.
			 * @param[in] cat Nombre de la categoría.
			 * @param[in] padre Puntero al nodo padre de la categoría.
			 * @remark @b Complejidad: @f$\Theta(|cat|)@f$
			 */
			Nodo( Nat id, const String &cat, Nodo *padre = NULL ) {
				this->id = id;
				this->cat = cat;
				this->padre = padre;
			}

			Nat id; /**< Id de la categoría. */
			String cat; /**< Nombre de la categoría (es igual a la clave del diccionario). */
			Nodo *padre; /**< Puntero al padre de la categoría. */
			aed2::Lista<Nodo *> hijos; /**< Lista de hijos de la categoría. */
		};

		/**
		 * Borra todos los nodos empezando por p.
		 * @param[in] p El nodo a partir del cual empezar a borrar.
		 * @remark @b Complejidad: @f$\Theta(n)@f$, donde n es la cantidad de nodos por debajo de @b p.
		 * @pre @b p no puede ser NULL.
		 */
		void borrarNodos( Nodo *p );

		Nodo *mRaiz; /**< Categoría raíz. */
		Nat mUltimoId; /**< Último id, listo para devolver. */
		DiccTrie<Nodo *> mCategorias; /**< Diccionario de categorías. */
	
	public:
		/**
		 * Iterador unidireccional no modificable del árbol de categorías.
		 */
		class Iterador {
			public:
				/**
				 * Estructura devuelta por el iterador.
				 */
				struct ItElem {
					/**
					 * Constructor de la estructura.
					 * @param[in] c Nombre de la categoría.
					 * @param[in] p Nombre de la categoría padre.
					 * @remark @b Complejidad: @f$\Theta(1)@f$
					 * @remark @b Alias: La estructura guarda referencias no modificables a
					 *         los argumentos @b c y @b p.
					 */
					ItElem( const String &c, const String &p ) : cat(c), padre(p) {}
					const String &cat; /**< Nombre de la categoría. */
					Nat id; /**< ID de la categoría. */
					bool tienePadre; /**< Indica si tiene padre o no.
					                   *  @li @b true si la categoría posee una categoría padre,
					                   *  @li @b false en otro caso. Sólo se encuentra en false para la categoría raíz. */
					const String &padre; /**< Nombre de la categoría padre, "" si no tiene padre. */
					Nat padreId; /**< ID de la categoría padre. */
				};

				/**
				 * Crea un iterador.
				 * Itera sobre los hijos de la raíz.
				 * @param[in] ac Árbol de categorías sobre el cual iterar.
				 * @remark @b Complejidad: @f$\Theta(1)@f$
				 */
				Iterador( const ArbolCategorias &ac ) { mIt = ac.mRaiz->hijos.CrearIt(); }


				/**
				 * Crea un iterador.
				 * Itera sobre los hijos de la categoría @b padre.
				 * @param[in] padre Categoría de la cual se desea iterar sobre sus hijos.
				 * @pre @b padre tiene que ser una categoría válida en el árbol de categorías.
				 * @remark @b Complejidad: @f$\Theta(|padre|)@f$
				 */
				Iterador( const ArbolCategorias &ac, const String &padre ) { mIt = ac.mCategorias.Obtener(padre)->hijos.CrearIt(); }

				/**
				 * Crea un iterador.
				 * Itera sobre los hijos de la categoría apuntada por el iterador pasado como argumento.
				 * @param[in] it Iterador que apunta a la categoría en la que se desea iterar sobre sus hijos.
				 * @pre @b it tiene que tener siguiente.
				 * @remark @b Complejidad: @f$\Theta(1)@f$
				 */
				Iterador( const ArbolCategorias &ac, const Iterador &it ) { mIt = it.mIt.Siguiente()->hijos.CrearIt(); }

				/**
				 * Indica si hay más elementos para iterar.
				 * @remark @b Complejidad: @f$\Theta(1)@f$
				 * @returns @b true si hay más elementos, @b false si no.
				 */
				bool HayMas() const { return mIt.HaySiguiente(); }

				/**
				 * Avanza al siguiente elemento.
				 * @remark @b Complejidad: @f$\Theta(1)@f$
				 */
				void Avanzar() { mIt.Avanzar(); }

				/**
				 * Obtiene el siguiente elemento.
				 * @remark @b Complejidad: @f$\Theta(1)@f$
				 */
				ItElem Siguiente() const;

			private:
				aed2::Lista<Nodo *>::const_Iterador mIt; /**< Iterador utilizado para iterar sobre la lista de hijos. */
		};
};

#endif
